package leetcode.cn;

import java.util.HashSet;

/**
 * @version 1.8
 * @Author Djx_hmbb
 * @Date 2023/11/12 16:42
 * @注释:力扣3.无重复字符的最长子串
 */
public class LengthOfLongestSubstring {
    /*
 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
--------示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
-------示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无
复字符的最长子串是 "b"，所以其长度为 1。
-------示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
-------提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成*/

    //优秀--自己写的代码!!!--------耗时,占用空间太长
    public static int lengthOfLongestSubstring1(String s) {
        char[] chars = s.toCharArray();//先将s传华为字符数组
        HashSet<Character> hashSet = new HashSet<>();
        int n = chars.length, len = 0;
        int right = 0, left = 0;
        while (left <= right && right < n) {
            //如果hashSet存在[r],则remove [l],l++
            //不存在,则存入并r++;
            if (hashSet.contains(chars[right])) {
                len = Math.max(len, right - left);
                hashSet.remove(chars[left++]);
            } else hashSet.add(chars[right++]);
        }
        return Math.max(len, hashSet.size());
    }


    //老师写的--代换Hash表--------优秀!!!
    public static int lengthOfLongestSubstring2(String ss) {
        char[] s = ss.toCharArray();
        //用数组代换Hash表
        int[] hash = new int[128];//这里的128刚好囊括了所有阿斯克码值(0-127)
        int right = 0, left = 0, ret = 0;
        while (right < s.length) {
            hash[s[right]]++;//让s[right]所在的阿斯克码值+1----入窗口
            while (hash[s[right]] > 1) {//说明该字母已存在
                hash[s[left++]]--;//让s[left++]所在的阿斯克码值-1----窗口
            }
            ret = Math.max(ret,right-left+1);
            right++;
        }
        return ret;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println("," + s + ",");
        int i = lengthOfLongestSubstring2(s);
        System.out.println(i);
    }


}
